'''
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array
'''
import bisect
from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        # >= 的最左位置，>=的最右位置
        n = len(nums)
        l = bisect.bisect_left(nums, target)
        if l == n or nums[l] != target:
            return [-1, -1]
        r = bisect.bisect_right(nums, target) - 1
        return [l, r]

    def searchRange2(self, nums: List[int], target: int) -> List[int]:
        # >= 的最左位置，<=的最右位置
        def bs_most_left(l, r):
            most_left = -1
            while l <= r:
                m = l + r >> 1
                if nums[m] >= target:
                    most_left = m
                    r = m - 1
                else:
                    l = m + 1
            return most_left
        def bs_most_right(l, r):
            most_right = -1
            while l <= r:
                m = l + r >> 1
                if nums[m] <= target:
                    most_right = m
                    l = m + 1
                else:
                    r = m - 1
            return most_right

        left = bs_most_left(0, len(nums) - 1)
        if left == -1 or nums[left] != target: return [-1, -1]
        right = bs_most_right(left, len(nums) - 1)
        return [left, right]

